package day_7_14;

import java.util.*;

public class Main3 {
    /**
     * 380. O(1) 时间插入、删除和获取随机元素
     * https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150
     */
    class RandomizedSet {
        List<Integer> nums;
        // <赋值，下标>
        Map<Integer,Integer> hash;
        Random random;

        public RandomizedSet() {
            nums = new ArrayList<>();
            hash = new HashMap<>();
            random = new Random();
        }

        public boolean insert(int val) {
            if(hash.containsKey(val)) {
                // 存在这个 val 值就是退出
                return false;
            }
            int index = nums.size();
            nums.add(val);
            hash.put(val,index);
            return true;
        }

        // 在remove的时候，用list末尾的那个元素替换移除的元素
        public boolean remove(int val) {
            if(!hash.containsKey(val)) {
                // 如果不存在就直接返回
                return false;
            }
            int index = hash.get(val);
            hash.remove(val);
            int a = nums.remove(nums.size() - 1);
            if(a != val) {
                hash.put(a,index);
                // 将 index 位置的值 赋值为 a值
                nums.set(index,a);
            }
            return true;
        }

        public int getRandom() {
            int index = random.nextInt(nums.size());
            return nums.get(index);
        }
    }
}
